package com.lsa.letcode.the34.searchRange;

public class Solution {
	private static final int[] NOT_FOUNT = new int[] { -1, -1 };

	public int[] searchRange(int[] arr, int target) {
		if (arr.length < 1 || arr[0] > target || arr[arr.length - 1] < target) {
			return NOT_FOUNT;
		}
		int left = leftBound(arr, target);
		if (left < 0) {
			return NOT_FOUNT;
		}
		return new int[] { left, rightBound(arr, target) };
	}
	
	int leftBound(int[] arr, int target) {
		int i = 0;
		int j = arr.length - 1;
		int mid = 0;
		int targetIdx = - 1;
		
		while(i <= j) {
			mid = (i+j) >>> 1;
			if (arr[mid] == target) {
				if (mid > 0 && arr[mid - 1] < target) {
					targetIdx = mid;
					break;
				}
				else if (mid == 0) {
					targetIdx = mid;
					break;
				}
				else {
					j = mid - 1;
				}
			}
			else if (arr[mid] < target){
				if (mid < arr.length - 1 && arr[mid + 1] == target) {
					targetIdx = mid + 1;
					break;
				}
				else {
					i = mid + 1;
				}
			}
			else if (arr[mid] > target){
				j = mid - 1;
			}
		}
		
		return targetIdx;
	}
	
	int rightBound(int[] arr, int target) {
		int i = 0;
		int j = arr.length - 1;
		int mid = 0;
		int targetIdx = - 1;
		
		while(i <= j) {
			mid = (i+j) >>> 1;
			if (arr[mid] == target) {
				if (mid < arr.length - 1 && arr[mid + 1] > target) {
					targetIdx = mid;
					break;
				}
				else if (mid == arr.length - 1) {
					targetIdx = mid;
					break;
				}
				else {
					i = mid + 1;
				}
			}
			else if (arr[mid] < target){
				i = mid + 1;
			}
			else if (arr[mid] > target){
				if (mid > 0 && arr[mid - 1] == target) {
					targetIdx = mid - 1;
					break;
				}
				else {
					j = mid - 1;
				}
			}
		}
		
		return targetIdx;
	}
}